package backdate;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

//https://leetcode.cn/problems/7p8L0Z/description/
//给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
public class LCR_084全排列2 {
    class Solution {
        private List<List<Integer>> res = new ArrayList<>();
        private List<Integer> output = new ArrayList<>();
        public List<List<Integer>> permuteUnique(int[] nums) {
            for(int i : nums)
                output.add(i);
            backtrack(0,nums.length);
            return res;
        }
        private void backtrack(int f,int n){
            if(f == n)
                res.add(new ArrayList<>(output));
            HashSet<Integer> set = new HashSet<>();
            for(int i=f; i<n; i++){
                if(set.contains(output.get(i))) continue;
                set.add(output.get(i));
                Collections.swap(output,f,i);
                backtrack(f+1,n);
                Collections.swap(output,f,i);
            }
        }
    }

}
